1. Field of the Invention
The invention generally relates to time series data modeling, and more particularly to Hidden Markov Models (HMMs) utilized to model both dependent and independent variables in multiple applications.
2. Description of the Related Art
Within this application several publications are referenced by Arabic numerals within brackets. Full citations for these and other publications may be found at the end of the specification immediately preceding the claims. The disclosures of all these publications in their entireties are hereby expressly incorporated by reference into the present application for the purposes of indicating the background of the invention and illustrating the general state of the art.
The term “asynchronous” is used herein to mean multiple events of interest that occur at different, but distinct, times. Hidden Markov Models [1] are a popular tool to model time series data and are widely used in fields such as speech recognition and bioinformatics. While modeling the data using HMMs, it is assumed that there is an underlying Markov process that generates the hidden state sequence, wherein observations are made at regular intervals conditioned on these states. However, for a number of reasons the latter assumption may not always hold. For example, when speech data is transmitted over a noisy channel before recognition, then some of the frames of data might be lost. Additionally, in speech systems it is well known that occasionally there are less speech frames for a particular phoneme than needed to fully traverse all the states [2]. Conventional approaches to solve these problems can be broadly divided into two categories:
First, if the actual time stamps of the missing frames are available, then interpolated values can be used to fill the missing observations. Once predicted, data is decoded using conventional HMMs [3]. However, one drawback of the interpolation approach is that one needs to know where the missing data is in order to properly interpolate values to fill in the missing data. Second, modifying the structure of the underlying HMM by adding a skip-arc (allows certain states to be skipped). The weights of the skip-arcs are either learned by training a modified model on data with missing frames or chosen in some ad-hoc manner. This new model is then used for decoding [2]. However, one drawback of the skip-arc approach is that it yields an over-generalization of the results.
FIG. 1 illustrates a conventional HMM expanded in time. Here, Si ε {1, . . . , N} and Oi ε {1, . . . , M} are random variables referred to as hidden states (S) and observations (O). The corresponding sequences of random variables are denoted as S={S1, . . . , ST}, O={O1, . . . ,OT}. The conventional HMM is characterized by parameter vector λ=(A, B, π), where A represents a transition probability matrix. A is a N×N matrix where αij=A(i,j)=P(St=i|St−1=j); B represents an observation probability matrix. B is a M×N matrix where bij=B(i,j)=P(Ot=i|St=j); and π represents an initial state probability matrix. Here, π is a N×1 matrix where π(i)=P(S1=i).
As such, because conventional HMMs rely on the assumption that observations are made at regular intervals, if this assumption does not hold, then there is likely to be a mismatch between the model and the data, which may subsequently degrade system performance (whatever system is being modeled). Therefore, due to the limitations to the approaches of modeling using the conventional HMMs, there is a need for a new and improved HMM modeling technique that overcomes the deficiencies of the conventional approaches.